package 栈和队列;

import java.util.Deque;
import java.util.LinkedList;

/**
 * ---------------------------------------------------------
 * <h></h>
 * <p>
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 *
 * 返回滑动窗口中的最大值
 *
 * 示例 1：
 *
 * 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
 * 输出：[3,3,5,5,6,7]
 * 解释：
 * 滑动窗口的位置                最大值
 * ---------------               -----
 * [1  3  -1] -3  5  3  6  7       3
 *  1 [3  -1  -3] 5  3  6  7       3
 *  1  3 [-1  -3  5] 3  6  7       5
 *  1  3  -1 [-3  5  3] 6  7       5
 *  1  3  -1  -3 [5  3  6] 7       6
 *  1  3  -1  -3  5 [3  6  7]      7
 * 示例 2：
 *
 * 输入：nums = [1], k = 1
 * 输出：[1]
 * 示例 3：
 *
 * 输入：nums = [1,-1], k = 1
 * 输出：[1,-1]
 * 示例 4：
 *
 * 输入：nums = [9,11], k = 2
 * 输出：[11]
 * 示例 5：
 *
 * 输入：nums = [4,-2], k = 2
 * 输出：[4]
 *  
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * -104 <= nums[i] <= 104
 * 1 <= k <= nums.length
 *
 *
 * 链接：https://leetcode-cn.com/problems/sliding-window-maximum
 *
 * </p>
 * Created by Frank on 2021/3/31.
 * <a href="mailto:frankyao10110@gmail.com">Contact me</a>
 * ---------------------------------------------------------
 */
public class _滑动窗口最大值 {
    public static void main(String[] args) {
        int[] nums = new int[]{9,10,9,-7,-4,-8,2,-6};
        int[] ans = maxSlidingWindow(nums, 5);
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];

        Deque<Integer> maxes = new LinkedList<>();

        for (int i = 0; i < nums.length; i++) {
            //当队列不为空且当前即将入队的值大于或等于队尾的值则将队尾出列
            //循环直到队列为空
            while (!maxes.isEmpty() && nums[i] >= nums[maxes.peekLast()]) {
                maxes.removeLast();
            }

            //将当前遍历到的值的下标入队
            maxes.offer(i);

            //从队头开始判断队列中的下标值是否在滑动窗口范围内
            int li = i - k + 1;
            if (li < 0) continue;

            //如果不在范围内，则出队
            if (maxes.peekFirst() != null && maxes.peekFirst() < li) {
                maxes.removeFirst();
            }

            //当前滑动窗口的最大值就是队列头部存储的下标对应的值
            ans[li] = nums[maxes.peekFirst()];
        }

        return ans;
    }

    public static int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums == null) return new int[0];
        int len = nums.length;
        if (len  < k || k == 1) return nums;

        int[] ans = new int[len - k + 1];
        int maxIndex = 0;
        for (int i = 0; i < k; i++) {//找到从0位置开始的当前滑动窗口的最大值下标
            if (nums[i] >= nums[maxIndex]) {
                maxIndex = i;
            }
        }

        //遍历剩下的值
        for (int li = 0; li < len - k + 1; li++) {
            int ri = li + k - 1;

            //如果遍历到的值大于之前的最大值则更新最大值下标
            if (nums[ri] >= nums[maxIndex]) {
                maxIndex = ri;
            }

            //如果遍历到的值小于之前的最大值
            //要看看之前的最大值下标是否在滑动窗口内，如果不在则找出以li为起点的滑动窗口的最大值后继续
            if (maxIndex < li) {
                maxIndex = li;
                for (int i = li; i < li + k; i++) {
                    if (nums[i] >= nums[maxIndex]) {
                        maxIndex = i;
                    }
                }
            }

            ans[li] = nums[maxIndex];
        }


        return ans;
    }
}
